package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/6/28
 * Description:
 * - 长度最小的子数组
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
 * <p>
 * 示例: 
 * <p>
 * 输入: s = 7, nums = [2,3,1,2,4,3]
 * 输出: 2
 * 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 * 进阶:
 * <p>
 * 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
 * <p>
 * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 **/
public class Que209 {

    public static void main(String[] args) {

        int s = 7;
        int[] nums = new int[]{2, 3, 1, 2, 4, 3};

        System.out.println(new Solution().minSubArrayLen(s, nums));
    }

    static class Solution {
        public int minSubArrayLen(int s, int[] nums) {
            int l = nums.length;
            int i = 0;
            int sum = 0;
            int min = l + 1;

            for (int j = 0; j < l; j++) {
                if (nums[j] == s) return 1;

                sum += nums[j];
                if (sum < s) continue;

                // 出队
                while (sum >= s) {
                    min = Math.min(j - i + 1, min);
                    sum -= nums[i++];
                }
            }
            return min == l + 1 ? 0 : min;
        }
    }

    static class Solution1 {
        public int minSubArrayLen(int s, int[] nums) {
            int l = nums.length;

            int[] res = new int[l];
            int[] idx = new int[l];

            for (int i = 0; i < l; i++) {
                for (int j = 0; j <= i; j++) {
                    if (res[j] >= s) continue;
                    res[j] = res[j] + nums[i];
                    if (res[j] >= s) idx[j] = i;
                }
            }

            int min = l + 1;
            for (int i = 0; i < l; i++) {
                if (idx[i] > 0 && idx[i] < min) min = idx[i];
            }
            return min > l ? 0 : min;
        }
    }
}
